perm filename LABEL.PUB[DOC,LMM] blob
sn#056032 filedate 1973-07-31 generic text, type T, neo UTF8
COMMENT ⊗ VALID 00017 PAGES
RECORD PAGE DESCRIPTION
00001 00001
00003 00002 .<< pub macros, declarations >>
00006 00003 . << title page >>
00007 00004 .TITL INTRODUCTION
00011 00005 .TITL PART A: DEFINITIONS
00017 00006 .HD PERMUTATIONS AND PERMUTATION GROUPS
00025 00007 .TITL PART B: SOLUTION TO THE LABELLING PROBLEM
00027 00008 .HD A Better Method
00033 00009 .HD LABEL RECURSION
00036 00010 .HD ORBIT RECURSION
00041 00011 .HD SPECIAL CASES
00045 00012 .HD FINAL TECHNIQUE
00051 00013 .TITL PART C: SUMMARY OF LABELLING STEPS
00054 00014 .TITL PART D: EXTENDED EXAMPLES
00057 00015 .HD |METHOD β(see Figure 11)|
00061 00016 .HD Labellings on the Octahedral skeletal framework.
00068 00017 .TITL ACKNOWLEDGEMENTS
00069 ENDMK
⊗;
.<< pub macros, declarations >>
.DEVICE XGP
.
.PAGE FRAME 56 HIGH 75 WIDE
.AREA TEXT LINES 4 TO 54 ;
.TITLE AREA HEADING LINES 1 TO 3 ;
.TITLE AREA FOOTING LINE 56 ;
.
.FONT 1 "BDR25.FNT[DOC,LMM]";
.FONT 2 "BDI25";
.FONT 3 "NGB25";
.FONT 4 "FIX25";
.FONT 5 "FIX13X";
.AT "β" ⊂ TURN ON "%{" }%1{TURN OFF⊃;
.AT "λ" ⊂ TURN ON "%{" }%2{TURN OFF⊃;
.AT "α" ⊂ TURN ON "%{" }%3{TURN OFF⊃;
.AT "ε" ⊂ TURN ON "%{" }%4{TURN OFF⊃;
.AT "~" ⊂ TURN ON "%{" }%5{TURN OFF⊃;
.
.<< footnote macros >>
.FOOTSEP←"------------------";
.COUNT REFERENCE INLINE PRINTING "↑1"
.AT "<<" LABEL ":" TEXT ">" ⊂
.LABEL: NEXT REFERENCE!;!;
.SEND FOOT ⊂
.PREFACE 1; SPREAD←1; INDENT 0,0; TURNON "{";
{REFERENCE! LABEL}TEXT
.TURNOFF
.BREAK ⊃ ⊃
.
.COUNT FIGGER INLINE PRINTING "Fig. 1"
.MACRO FIGURE(NUM,SIZ,FIGHEAD) ⊂
.BEGIN NOFILL;NEXT FIGGER!;
.!}α→→→ Figure NUM, FIGHEAD ←←←←←β
.END⊃
.
.<<label macros >>
.MACRO HD (HEADING) ⊂
.BEGIN IF LINES<10 THEN SKIP TO COLUMN 1 ELSE SKIP 2; NOFILL;BREAK;
αHEADINGβ
.END; ONCE PREFACE 0;⊃
.
.MACRO TITL (TITLE) ⊂
.BEGIN IF LINES<10 THEN SKIP TO COLUMN 1 ELSE SKIP 2; BREAK; CENTER;
αTITLEβ
.END;⊃
.
.MACRO GRAF (HDNG) ⊂
αHDNG.β
.⊃
.
.MACRO I6 ⊂ INDENT 6,6,6; SPREAD←1; PREFACE 1; ⊃
.MACRO SPACE1 ⊂ SPREAD←1; PREFACE 2; BREAK; ⊃
.MACRO SPACE2 ⊂ SPREAD←2; PREFACE 3; BREAK; ⊃
.
.TURNON "↑↓[]&→"
.
. << title page >>
.BEGIN CENTER
LABELLING OBJECTS HAVING SYMMETRY
L. Masinter, N.S. Sridharan, D. H. Smith
Computer Science Department
Stanford University
Stanford, California
May, 1973
.END
.GROUP SKIP 5
.BEGIN INDENT 6,6,6
ABSTRACT. An algorithm for finding a complete set of non-equivalent
labellings of a symmetric object and applications of the algorithm
to problems in chemistry are presented.
.END
.
.EVERY FOOTING(,{PAGE},)
.
.SKIP TO COLUMN 1
.SPACE2;
.TITL INTRODUCTION
The class of combinatorial problems dealing with finding a complete
set of non-isomorphic objects under varying constraints and concepts
of isomorphism, has wide applications in a variety of fields. The
problem attacked in this paper is one of finding all distinct ways
to assign a given number of labels or colors to the parts of a
symmetric object when it is also known how many parts get each of
the labels or colors. In chemistry, one manifestation of this
problem is to make all assignments of ligands (from a fixed set) to
a given carbocyclic skeleton<<ML:Masinter, L., Sridharan, N. S.,
et.al., Applications of Artificial Intelligence for Chemical
Inference - XII, submitted, 1973, λJ. Amer. Chem. Soc.β>. Part A of
this paper may be read as a brief tutorial on the nature of the
problem and an introduction to the terminology found in more
technical treatments. Part B is a textual description of a method
for the solution of this type of problem. Part C is a summary of the
procedure in a more algorithmic form; an even more formal
description and a proof of correctness is available elsewhere<<BROWN:
Brown, H., Masinter, L., Hjelemeland, L., Constructive Graph Labelling
Using Double Cosets, submitted, 1972, λDiscrete Mathematicsβ; also,
Stanford Computer Science Memo ??, Stanford University.>.
Part D gives examples and applications of
this algorithm in both organic and inorganic chemistry.
This problem is encountered in a wide range of applications beyond
chemistry-- within many areas of graph theory and combinatorics, for example.
It has been known how to compute the number of solutions<<DEBRUIJN:
De Bruijn, N. G., Generalization of Polya's Fundamental
Theorem in Enumerative Combinatorial Analysis, λNedarl. Akad.
Wentesh. Proc. Ser. A, α62β, (1959), 59-69>↑,
<<POLYA:De Bruijn, "Polya's Theory of Counting," λApplied Combinatorial
Mathematicsβ, E. Beckenbach (ed.), Wiley, New York, 1964, pp 144-184.>,
but an efficent method of actually constructing the solutions has
not previously been published<<PERLMAN:see, however,
Perlman, D. M., Isomorph Rejection on Power Sets, (unpublished), University
of California San Diego.>.
.TITL PART A: DEFINITIONS
.HD SYMMETRY AND ITS RELATIONSHIP TO LABELLING
Consider the special case of the general problem: suppose all of the
labels are distinct. This means that, for example, one wishes to
number the faces of a cube with the numbers {1, 2, 3, 4, 5, 6}, or the
"nodes" (atom positions in a graph) of the decalin skeleton (Fig. 1)
with numbers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. There are n! (n factorial)
ways of labelling where n is the number of parts. If the object has
no symmetry then each of these n! ways are distinct from the rest.
However for the decalin skeleton (where n! = 10! = 3,628,800 ways)
there is some symmetry. First one picks, arbitrarily, one of the
numberings as a point of reference (Fig 2a). Some of the 10! ways
are different (Fig 2b); some of them are essentially the same (Fig
2c).
.Figure 1,9,The Decalin Skeleton
.Figure 2,9,Three of the 10! numberings of the Decalin Skeleton.
Intuitively, Figs 2a and 2c are equivalent because one could take
2a, flip it over the 3-8 axis, and get 2c. There is another way of
determining the "sameness" of such numberings which is easier in the
more complicated cases and is in general more suited to computer
application:
.BEGIN I6
αDEFINITION:β two numberings of the nodes of a graph are
λequivalentβ if the connection tables with the respective numberings
are identical when the node numbers are written in ascending order
and each "connected to" list is in ascending order.
.END
Table I contains the respective "connection tables" of the structures in Fig. 2.
Note
that the connection table for Fig 2c is identical to that of Fig 2a;
that of Fig 2b is different.
.BEGIN VERBATIM GROUP SELECT 4
__________________________________________________________________
Table I.
Structure (2a) Structure (2b) Structure (2c)
node|connected | node|connected | node|connected
| to | | to | | to
| |
1 2,1O | 1 8,9 | 1 2,1O
2 1,3 | 2 7,3 | 2 1,3
3 2,4,8 | 3 2,6 | 3 2,4,8
4 3,5 | 4 6,8,1O | 4 3,5
5 4,6 | 5 9,1O | 5 4,6
6 5,7 | 6 3,4 | 6 5,7
7 6,8 | 7 2,8 | 7 6,8
8 3,7,9 | 8 1,4,7 | 8 3,7,9
9 8,1O | 9 1,5 | 9 8,1O
1O 1,9 | 1O 4,5 | 1O 1,9
____________________________________________________________________
.END
This definition means, among other things, that properties such as valency
are preserved: If two numberings are equivalent and in the first, node
1 is trivalent, then in the second, node 1 is trivalent. If there are
other properties of the nodes (they are already colored or labelled, for example),
then this definition can be extened to include the preserving of those
properties.
For example, suppose there are atom names associated with (some of)
the nodes of the graph. Then one can define equivalent numberings
to be those which not only have identical connection tables, but also
the same atom names
for the corresponding nodes. Then Fig 3a would still be equivalent
to Fig 3c but no longer to Fig 3b since, although the connection tables
of 3a and 3b are identical, node 1 in Fig 3a is labelled with an "N" while
in 3b it unlabelled.
.Figure 3,9,Partially labelled graphs reduce the equivalencies.
.HD PERMUTATIONS AND PERMUTATION GROUPS
Given a numbering of a structure, one can use a condensed notation to write down
other numberings in terms of the first (Table II). In the 2b case,
the row of numbers means that, in sequence, the node numbered 1 in
the reference numbering 2a is now numbered 2, the node originally
numbered 2 is now numbered 10, and so on. All of these are written
down with respect to the original "reference" numbering of figure
2a.
.BEGIN NOFILL GROUP SELECT 4
_________________________________________________________________
Table II
Condensed Notation for Numberings
Figure 2a numbers: 1 2 3 4 5 6 7 8 9 10
Figure 2b numbers: 2 7 8 1 9 5 10 4 6 3
Figure 2c numbers: 5 4 3 2 1 10 9 8 7 6
_________________________________________________________________
.END
One can conceptualize a numbering as a transformation or as a
function: The transformation π for 2c is π↓2↓c(1)=5, π↓2↓c(2)=4,
π↓2↓c(3)=3, ... π↓2↓c(10)=6. These transformations are
λpermutationsβ: one to one mappings from the integers {1,2,...,n} to
themselves. The transformation for the "reference" numbering is the
identity i(x)=x. It can be shown that whatever the graph, the set of
transformations satisfying the "equivalency" requirement above
satisfies the property of a group. One may then say:
.BEGIN I6
The λsymmetry groupβ of a graph is the set of all transformations which
yield identical connection tables. (If there are other properties
to be considered, one may include them as part of the connection table).
For the decalin skeleton there are 4 permutations in the symmetry group.
.END
.BEGIN NOFILL GROUP SELECT 4
_____________________________________________________________________
Table III
The Symmetry Group
of the Decalin Skeleton
π↓i 1 2 3 4 5 6 7 8 9 10
π↓v 5 4 3 2 1 10 9 8 7 6
π↓h 10 9 8 7 6 5 4 3 2 1
π↓[180] 6 7 8 9 10 1 2 3 4 5
____________________________________________________________________
.END
These correspond directly to the intuitive geometric symmetries
π↓i=identity, π↓h=reflection about horizontal axis, π↓v=reflection
about vertical axis, π↓[180] = rotation 180 degrees.
It is not too difficult for a computer program to figure out the symmetry
group of a graph given its connection table<<GROUPCALC:
this needs to be described>.
This definition deals with the symmetry of the λnodesβ of a graph.
In many cases, one might wish to label the λedgesβ (interconnecting
lines) of a graph. In this case, the symmetry group on the edges
rather than on the nodes is required. It is very easy to calculate
this group from the group on the nodes. Let the numbering for each edge
in the graph be the unordered pair of numbers of the nodes that form the end-points.
Then the corresponding permutations can be obtained as follows:
.BEGIN NOFILL
π↓i{n↓1,n↓2}={π↓i(n↓1),π↓i(n↓2)}
.END
This is most easily shown by way of an example. (Table IV).
.BEGIN NOFILL GROUP SELECT 4
__________________________________________________________________
Table IV
Permutation Group of Decalin Skeleton acting on the edges
π↓i 1-2 2-3 3-8 3-4 4-5 5-6 6-7 7-8 8-9 9-10 1-10
π↓v 4-5 3-4 3-8 2-3 1-2 1-10 9-10 8-9 7-8 6-7 5-6
π↓h 9-10 8-9 3-8 7-8 6-7 5-6 4-5 3-4 2-3 1-2 1-10
π↓[180] 6-7 7-8 3-8 8-9 9-10 1-10 1-2 2-3 3-4 4-5 5-6
____________________________________________________________________
.END
Finding the group of an object is a special kind of labelling problem.
Given one way of numbering (labelling with distinct labels) the parts
of the object, one finds all other ways which are equivalent. The labelling
problem attacked in this paper is the converse: to find a maximal
list of labellings, none of which are equivalent to each other. In
general the set of all posssible labellings can be split into subsets,
such that:
.BEGIN I6
1) If two labellings are in different subsets, they are not equivalent.
2) If two labellings are in the same subset, they are equivalent.
.END
These subsets are called λequivalence classesβ of labellings.
The relationship of finding the group, and of finding labellings
where all the labels are distinct, can be viewed as follows:
Take the n! possible labellings and lay them out in a matrix: each
row will contain one equivalence class. (It can be shown that in this
special cases where the labels are distinct, all of the equivalence classes
are of the same size). To find the group, one needs to find a row.
To find the labellings, one needs to pick one element from each row.
.Figure 4,10,"Equivalence classes, Groups, and Labellings"
.TITL PART B: SOLUTION TO THE LABELLING PROBLEM
.HD A Naive Method
An obvious method to find the distinct labellings would be to
generate all n! of the possible ones, and for each one to check if
an equivalent one was previously generated. Unfortunately, this method
takes an exhorbitant amount of computation (proportional to n! squared).
Below a method is discussed which takes an amount of time roughly
proportional to the number of solutions (i.e. the number of
equivalence classes of labellings) and requires only knowledge of
the symmetry group. Thus it is useful for labelling objects using
their geometric symmetry
.reference! ml}
as well as the topological symmetry defined above.
.HD A Better Method
.GRAF Special case: distinguish 1 node
First consider the special case where there are only two types of
labels such that there is one label of the first type and all the
rest of the second. (E.g., color one red, and the rest green, or
label one N and the rest C.) Intuitively, for the decalin skeleton,
one can see that there are three classes of symmetric nodes, or
λorbitsβ, marked with "⊗", "+" and "&" in Fig. 5, and that each
distinct labelling corresponds to selecting one node from each type
(see Fig 6.)
~(CHECK TO MAKE SURE THAT SYMBOLS ARE APPROPRIATE TO FIGURE)β
.Figure 5,9,Orbits in the Decalin Skeleton
.Figure 6,9,Three Labellings of Decalin with 1 N and 9 C's.
Thus there are three distinct labellings (the ten possible labellings
split into three equivalalence classes).
.GRAF Computing orbits
In general, the parts of a symmetry object split into different
orbits (sometimes there is only one type, as in the faces of a cube, or
the nodes of the cyclohexane skeleton). To label the
parts of an object such that one is distinguished, it is necessary only
to find the orbits and then, for each type, pick one of the parts in
that type arbitrarily. Note that if the object has no symmetry each
type has exactly one part in it.
It is very simple to find the different types from the table of the
symmetry group: if one writes out the group, as in Table III, with
each permutation as a row, then the numbers in each column, taken as
a set, form an orbit. The orbits of the group in Table III are:
{1,5,6,10}, {2,4,7,9}, {3,8}.
After finding the set of orbits, one then can do the special
labelling described above (distinguishing only one node): the number
of distinct labellings is the number of orbits. Each corresponds to
selecting an element from a corresponding orbit and labelling it.
For a convention, the first element of each orbit
should be chosen (i.e. the one with the smallest number in the
reference numbering).
.GRAF The reduced symmetry group
Once a group has been calculated for a structure, many times one
wants to know what the group is after some labels have been
attached. The group of a labelled structure is always a λsubsetβ of
the group of the unlabelled structure. Thus one needs to know which
permutations in the group must be thrown out. To do this, write the
"labels" associated with each node next to the node number in the
permutation table as in Table II. If in any column, there is an
element which has a different label than the label in the
"reference" numbering (identity permutation), then that row can be
discarded. That is, a permutation is valid if and only if the
structure "looks the same" after its node numbers are permuted.
Only permutations in the original group can possibly yield
structures which do look the same; however, because of the
labelling, some of these permutations may yield disimilar
structures. These permutations are the ones that must be discarded.
.GRAF Reduction techniques
In the general labelling problem, there are two important techniques used to
reduce the problem. The first is called λlabel recursionβ
<<RECUR:A λrecursiveβ technique is one which is defined in terms of
itself. It is only necessary that at each step the problem is reduced,
and that a terminating condition is eventually met. Here the general
solution of the labelling problem is described in terms of less
complicated labellings. Several special cases (terminating
conditions) are also defined.>
and the second λorbit recursionβ. The idea behind label recursion is
that one can do one label at a time. The idea behind orbit
recursion is that one can label one orbit at a time. These
reductions are discussed in detail below.
.HD LABEL RECURSION
If one is given many (more than 2) kinds of labels, say n↓1 of
type 1, n↓2 of type 2, ... n↓k of type k, one may proceed as follows:
Solve the labelling problem for n↓1 of one type of label
and n↓2+n↓3+...+n↓k of another type. (Call the second type of label
"blank"). The result will be a list of partially labelled
objects (along with their reduced symmetry groups).
Take each
of the results and label the "blank" parts with n↓2 labels of
one kind, n↓3 of another, ... ,n↓k of another. It has been proved
.REFERENCE! BROWN} that the results will be a list of all distinct solutions to the
original problem. For example, to label the decalin skeleton with
1 label "N", 1 label "S" and 8 labels "C", one first labels with
1 "N" and 9 "blanks" obtaining the 3 results in figure 7a.
(Fig 7a1, 7a2, 7a3). There are now 3 new problems: to label
the "blanks" of Figs. 7a1-3 under their respective reduced symmetry,
with 1 "S" and 8 "C"'s. In Figs 7a1 and 7a2, there is no symmetry
left and so each of the "blanks" has its own orbit; thus
there are 9 distinct labellings apiece. In Fig. 7a3 there
are 5 orbits under the reduced symmetry, and thus there are 5
additional possiblities (Fig 7b).
.Figure 7,15,|Labellings with 1 N, 1 S, and 8 C's.|
.HD ORBIT RECURSION
There are 3 cases in the problem of 1 N, 9 C on the decalin skeleton.
.BEGIN NOFILL
(case 1) 1 N goes to orbit {1,5,6,10}.
(case 2) 1 N goes to orbit {2,4,7,9},
(case 3) 1 N goes to orbit {3,8}.
.END
There is only one possibility in each of these cases.
Suppose there were 3 N's. Then there would be 9 cases. (Table IV).
.BEGIN VERBATIM GROUP SELECT 4
_________________________________________________________________
Table IV.
(3 N's on a Decalin)
# N's going to
case orbit orbit orbit
number {1,5,6,10} {2,4,7,9} {3,8}
1 3 0 0
2 2 1 0
3 2 0 1
4 1 2 0
5 1 1 1
6 1 0 2
7 0 3 0
8 0 2 1
9 0 1 2
_________________________________________________________________
.END
In some of these cases there are more than one possibility (cases
2, 3, 4, 5 and 8). However, every labelling fits into one of
these cases, and labellings from different cases cannot be equivalent.
Thus, each of these cases can be done independently, and the results
collected together. To do any one of the cases, the labellings of the
orbits can be done sequentially. That is, the rows of Table IV can be
done independently, and for each row the columns can be done from left to
right.
Considering case 5, one can first label one of {1,5,6,10} with one N, (and the
rest "blanks"). Since {1,5,6,10} is an orbit, one can chose node 1; the result
is Fig 8.
.Figure 8,9,|1 N to orbit {1,5,6,10}|
Second, one labels {2,4,7,9} with 1 N (and 3 blanks). Note that {2,4,7,9} is no
longer an orbit under the reduced group. Stick to the original plan-- it is
necessary to find λnewβ orbits under the reduced group to label {2,4,7,9}.
Since there is no symmetry left, each of {2,4,7,9} falls into its own orbit.
The "special case" described below under "No Group" can be used directly
to find the 4 solutions (Fig 9).
.Figure 9,12,Second step of case 5
Then, for each of these solutions, {3,8} must be labelled with 1 N
(and 1 blank). The final result is 8 possibilities for case 5, none
of which has any remaining symmetry.
.HD SPECIAL CASES
There are several special cases of labellings in which the problem
can be reduced or solved immediately. Although these special cases
may be amenable to the more general algorithm, their solution is
computationally simpler.
.GRAF Only one type of label
If the number of labels (of a given type) is the same as the number of
objects, then there is exactly one way of doing the labelling. This
check for this special case is necessary, since in orbit recursion,
often the sub-problem is of this form; n↓1=n, and n↓2=0 or vice versa.
.graf Only one of a given label
Already mentioned was the case
where there was one label of one kind and n-1 of the other; it was only
necessary to find the orbits, and label one element arbitrarily from
each of the orbits.
One might note here that the order in which one applies the labels in label
recursion is arbitrary
and thus if there is only one of any of the labels, then this special case
can be applied immediately.
.graf No group
When there is no symmetry left and there are two label types (n↓1 of the first
type, n↓2 of the second, n↓1+n↓2=n, the number of objects to be labelled),
the labelling reduces to a simple
combinatorial problem: given n distinct objects, find all ways of selecting
n↓1 of them. This can be done by the following recursive algorithm:
.BEGIN NOFILL
To find all selections of k objects out of set S whose size is n:
1) if k = 0 then there is only one selection, the empty set.
2) if k > n then there are no possible selections.
3) Otherwise, pick an element x from S.
a) Find all selections of k objects out of the set S-{x}.
b) Find all selections of k-1 objects out of the set S-{x};
to each of these, add the element x.
.END
A k-subset of a set S (a k-subset is a subset with k elements) either
contains an element x or not. In case 3a, one finds those selections
which do not contain x. In case 3b, one finds those selections which do.
However, each of these cases are simpler than the original selection problem;
the size of the set S reduces, as well as the value of k. The terminating
conditions, k=0, or k greater than the size of the set S, insure that
the process will halt.
.HD FINAL TECHNIQUE
It has been now shown that every problem can be reduced to cases
where there are only two types of labels, n↓1 of the first, and n↓2
of the second, (n↓1+n↓2=n, the number of nodes to be labelled),
both n↓1 and n↓2 > 1, and there is only one orbit. No more
simple reductions are left.
One solution, however, is another trick. Pick the first node and label
it, calculating the reduced symmetry group and new orbits.
Label the rest of the nodes (under the reduced group) with n↓1-1
labels of type 1 and n↓2 labels of type 2. The result will
contain a representative of each equivalence class of labellings;
however, if n↓1>2 then there may be some duplicates (i.e., two or more
of the results may actually be equivalent).
.hd special kludges for fast programs by Larry Masinter
.begin nofill
(this section to be written?)
(this section to be written?)
(this section to be written?)
(this section to be written?)
(this section to be written?)
(this section to be written?)
(this section to be written?)
.end
For example, the cyclohexane skeleton has a group of order twelve
(has twelve permutations), and there is only one orbit. To label
it with three N's, one labels node 1 with a N, calculates the
reduced group and new orbits; then finds the various cases for
distributing the remaining two N's among those orbits. (Table V.)
Then for each case, do each orbit sequentially. Cases 1, 3, 4
and 5 are fairly straightforward; in case 2, first label {1,2}
with 1 N. (Figure 9). Now the group reduces even further, and
one gets the two results depicted in Figure 9b.
Note that cases 1 and 2a are equivalent as well as 2b, 3, and
5. What to do? Fortunately, there is a good way of throwing
out the impostors without having to check each of the results
against each of the others for equivalency.
If there is a permutation π in the group, such that
.BEGIN NOFILL
π (labelled set) > labelled set
.END; CONTINUE
then the labelled set
is an impostor-- throw the bum out. Furthermore, every
impostor is detected this way. All that is necessary is
that when doing these "lower level" labellings, that one is
careful to pick the "first" element of each orbit to label
and the "first orbit" when there are a choice of orbits.
.BEGIN GROUP NOFILL SELECT 4
____________________________________________________________
Table V
cases for 2 N's on
{2,3,4,5,6} of cyclohexane
case {2,6} {3,5} {4}
1 2 - -
2 1 1 -
3 1 - 1
4 - 2 -
5 - 1 1
____________________________________________________________
.END
Fortunately, this technique is rarely necessary -- usually
in the course of a computation, the "special cases" catch
almost everything. For example, to label the decalin
skeleton, it is never needed since even when one is labelling
say orbit {2,4,7,9}, there is either 1, 2, n-1 or n-2 labels
to be attached. For the cyclohexane skeleton, it is only
needed if there are 3 of one label and 3 of another; if there
were 3,2 and 1 of three respective label types for example,
just do the single label
first -- the group will then reduce and again this "final
technique" will not be necessary. Only in cases where
there is an orbit with
at least 6 elements and there are at least 3 of each of
the label types is this technique required.
.TITL PART C: SUMMARY OF LABELLING STEPS
.BEGIN SPREAD←1; PREFACE 1; INDENT 0,3,3
1) Calculate the group, if not previously calculated.
2) If there are more than 2 different node types, do the entire
labelling process with 1 of the label types, and the rest "blanks";
then for each of the solutions obtained, label the "blanks" with the
remaining label types using the reduced symmetry group and collect
the results.
3) Otherwise,
.BEGIN INDENT 3,6,6
a) Find the orbits.
b) If more than one orbit, then
.BEGIN INDENT 6,9,9
1) Find the different "cases" -- ways of distributing the labels
among the orbits.
2) For each case,
.BEGIN INDENT 9,12,12
a) Label the first orbit.
b) Label the rest of the orbits using the reduced symmetry group
obtained from a), and collect the results.
.END END
c) Otherwise (only 1 orbit and 2 label types):
.BEGIN INDENT 6,9,9
1) If there is only one of one of the label types, pick the "first"
node and label it with that label type. This is the only distinct
possibility.
2) Otherwise if there are two of one of the label types, label the
first node with that label type, calculate the reduced symmetry
group and new orbits, and from each of the new orbits, pick the
"first" node. The solutions consist of those possibilities (one for
each new orbit).
3) Otherwise, (3 or more of each label type, and one orbit) label
the "first" node, calculate the reduced symmetry group, label the
rest of the nodes under the reduced group, and for each of the
results, check if for every permutation π in the original group that
.BEGIN NOFILL
π(labelled set)≥labelled set
.END
.CONTINUE
If this is not true of a labelled set, discard it
as a solution. The result is every such labelling
that satisfies this property.
.END END END
.TITL PART D: EXTENDED EXAMPLES
.HD |Study of Diels-Alder Ringsβ<<SIMEK:proposed by Jan Simek, Chemistry
.Department, Stanford University.
.Research Proposal (unpublished), February, 1973.>|
The labelling algorithm has been used to define the scope and
boundaries of the Diels-Alder reaction, a well-known and commonly
used synthetic reaction. The reaction is shown in Figure 10, and is
defined as the 4+2 cycloaddition of an olefin, termed the
dienophile, with a conjugated diene, leading to the formation of a
cyclohexene-type of ring system (Diels-Alder Ring).
.FIGURE 10,10,Diels-Alder reaction
The method used by the program to generate Diels Alder Rings is
described below, followed by an example of the labelling procedure.
The program generated 1176 Diels-Alder Rings using any combination
of C,N,O and S. Other atoms such as P could have been included but
were deemed not interesting to us. A comparison of the computer
print-out with the Ring Index (which covers the literature through
1963) revealed that only 224 (about 19% of 1176) are "known" systems.
A ring system was said to be known if the same sequence of atoms had
been reported regardless of number or position of unsaturations. The
complete list of Diels-Alder Rings is richly suggestive to the
synthetic chemists and may serve to increase the information on the
scope of the Diels-Alder reaction.
.Figure 11,20,Diagram of Method of Generation
.HD |METHOD β(see Figure 11)|
.graf Step 1
The initial pot of atoms consisted of C↓6N↓6O↓4S↓4. The number
of oxygens and sulfurs was limited to four, because no Diels-Alder
ring can be made with five or six bivalent atoms, owing to valence
restrictions. A list of all possible 76 compositions of 6 atoms was
produced using a purely combinatorial procedure.
.graf Step 2
Eleven of the 76 compositions were eliminated, again owing
to valence limitations. An example of the eleven compositions
eliminated is O↓3S↓3.
.graf Step 3
For each of the 65 remaining compositions, the Diels-Alder
ring skeleton was labelled with the atoms, while ensuring valence
constraints were satisfied.
.graf Step 4
The results from all labelling steps were collected, without
needing to check for duplicates. The labelling algorithm guarantees
that the lists were irredundant.
.graf Example of labelling
An example of a valid composition is C↓4O↓2.
Diels-Alder rings formed with this composition can only have carbons
double bonded to each other (Figure 12). The atoms remaining to be
assigned are C↓2O↓2 and the ring positions are numbered 1,2,3,4.
.FIGURE 12,12,Diels-Alder Example A
.GRAF Verification by Enumeration
The results of of the labelling procedure can be verified by
combinatorial counting techniques
.REFERENCE! POLYA}↑,
.REFERENCE! DEBRUIJN}.
The following derivation follows closely from that in
Liu<<LIU:ββLiu, Introduction to Comb. Math, McGraw-Hill, 1968>.
.begin nofill SELECT 4
Cycle Index of Group=PG = 1/2(y↑4&↓1+ y↑2&↓1)
Pattern Inventory is 1/2 (x↑1&↓1+ x↑1&↓2)↑4+ (x↑2&↓1+ x↑2&↓2)↑2
= 1/2 (x↑4&↓1+ x↑4&↓2+ 4x↑3&↓1x↓2+ 6x↑2&↓1x↑2&↓1+4x↓1x↑3&↓2)
+ (x↑4&↓1+ x↑4&↓2+ 2x↑2&↓1x↑2&↓2)
= 1/2 2x↑4&↓1+ 2x↑4&↓2+ 8x↑2&↓1x↑2&↓2+ 4x↑3&↓1x↓2+ 4x↑3&↓2x↓1
= x↓1&↑4+ x↓2&↑4 + 4 x↓1&↑2x↓2&↑2 + 2x↓1&↑3x↓2+ 2x↓2&↑3x↓1
showing that there are precisely these number of labellings:
labels #labellings
C C C C 1
S S S S 1
C C S S 4
C S S S 2
C C C S 2
.end
The third entry in the table verifies our labelling with C↓2S↓2 in four
ways.
.HD Labellings on the Octahedral skeletal framework.
This example is concerned with the geometric
isomers of structures with octahedral symmetry.
(Figure 13).
.FIGURE 13,8,Octahedral Skeletal Framework
.begin nofill
_________________________________________________________________
Labellings on Octahedral Skeletal Framework
Group is:
i (1 2 3 4 5 6)
r↓1 (1 3 5 4 6 2)
r↓2 (1 5 6 4 2 3)
r↓3 (1 6 2 4 3 5)
v↓1 (4 5 3 1 2 6)
v↓2 (4 2 6 1 5 3)
v↓3 (4 3 2 1 6 5)
v↓4 (4 6 5 1 3 2)
Orbits: {1 4}, {2 3 5 6}.
Example with labels (A A A A B B)
Number of labels A = 4
Number of labels B = 2
Partitioning Labels into Orbits:
Case number of A's assigned to orbit:
# {1 4} {2 3 5 6}
1 2 0
2 1 1
3 0 2
Case 1. To map A A --> {1 4}
and A A B B --> {2 3 5 6}
Map A A --> {1 4} (trivial case)
New group i, r↓1, r↓2, r↓3, v↓1, v↓2, v↓3, v↓4
New orbits {2 3 5 6}
To map A A B B --> {2 3 5 6}
Case 1.1. Assign A --> 2
New group i,?? ???????? fill in
New orbits {5},{3 6}
Case 1.1.1. Assign A --> 5
Remaining B B --> {3 6}
1 labelling (A A B A A B)
Case 1.1.2. Assign A --> 3
Remaining B B --> {5 6}
1 labelling (A A A A B B)
Case 2. To map A B --> {1 4}
and A A A B --> {2 3 5 6}
Assign A --> 1 and B --> 4
New group i, r↓1, r↓2, r↓3
New orbits {2 3 5 6}
To map A A A B --> {2 3 5 6}
Case 2.1. Assign B --> 2
To map A A A --> {3 5 6}
1 labelling (A B A B A A)
Case 3. To map B B --> {1 4}
and A A A A --> {2 3 5 6}
Assign B --> and B --> 4
New group i, r↓1, r↓2, r↓3, v↓1, v↓2, v↓3, v↓4
New orbit {2 3 5 6}
To map A A A A --> {2 3 5 6}
1 labelling (B A A B A A)
.FIGURE X,9,|Four labellings of Octahedral Skeleton with Labels (A A A A B B)|
Example with Labels A B C D E F
Case 1. A --> orbit {1 4}
A --> 1
new group i, r↓1, r↓2, r↓3
new orbits A1 = {2 3 5 6}
A2 = {4}
Assign label B
Case 1.1. B --> orbit A1
B --> 2
new group i
new orbits {3} {4} {5} {6}
CDEF --> 3,4,5,6
4! = 24 labelling generable with no further
involvement of permutation group.
Case 1↓2. B --> orbit A2
B --> 4
new group i, r1, r2, r3
new orbits AA1 = {2 3 5 6}
Case 1.2.1 C --> orbit AB1
C --> 2
new group i
new orbits {3} {5} {6}
DEF --> 3 5 6 6 labellings
Case 2. A --> orbit {2 3 5 6}
A --> 2
new group i,
new orbits B1 = {1 4}
B2 = {5}
B3 = {3 6}
Case 2.1. B --> orbit B1
B --> 1
new group i
new orbits {3} {4} {5} {6}
CDEF --> 3 4 5 6
24 labellings
Case 2.2. B --> orbit B2
B --> 5
new group i,? ???? fill in
new orbits BB1 = {1 4}
BB2 = {3 6}
Case 2.2.1. C --> orbit BB1
C --> 1
new group i
new orbits {3} {4} {6}
DEF --> 3 4 6 6 labellings
Case 2.2.2. C --> orbit BB2
C --> 3
new group i
new orbit {1} {4} {6}
DEF --> 1 4 6 6 labellings
Case 2.3. B --> B3
B --> 3
new group i
new orbit {1} {4} {5} {6}
CDEF 1 4 5 6 24 labellings
90 unique labelings all together.
Verification: When all labels are different the total number of
labellings
(# labels)! 6!
= -------------- = ---- = 90 labellings
(size of group) 8
.end
.TITL ACKNOWLEDGEMENTS
We gratefully acknowledge the contributions of
Jan Simek, who proposed the application in Part D,
Larry Hjelmeland who formulized the initial problem,
Professor Harold Brown, who proved the correctness of the original algorithms, and
Professor Joshua Lederburg, whose advice and guidance has always
been an inspiration.